This invention pertains to computer systems and other information handling systems and, more particularly, to a computer system having a distributed scheduling algorithm for the transfer of various classes of data (e.g., real time data, loss sensitive data and non-real time data) over a bus.
Data to be transferred from one point to another can be classified into one of several categories depending on how critical it is to transfer the data within a specified time limit, and the tolerance for loss of any portion of the data. Four classifications of data are described immediately below.
"Hard real time data" is data that must be transferred within a specified time limit, i.e., before a "deadline". Failure to transfer any portion of the data before the deadline is catastrophic because critical data will be lost. Thus, the performance objective for the transfer of hard real time ("HRT") data is "no missed deadlines" and, consequently, no lost data.
"Soft real time data" is data that should be transferred within a specified deadline and failure to transfer before the deadline results in lost data, but loss of some data is tolerable. The performance objective for the transfer of soft real time ("SRT") data is "low percentage of missed deadlines" and, consequently, a low percentage of lost data.
"Loss sensitive data" is data that has no deadline within which it must be transferred. Any loss of data, however, is intolerable. Thus, the performance objective for loss sensitive ("LS") data is "minimal lost data". Note that delay is irrelevant when measuring the performance of loss sensitive data transfers. In other words, it doesn't matter how long it takes to get there, as long as all the data gets transferred.
"Non real time data" is also data that has no deadline within which it must be transferred. But the performance measurement for non-real time ("NRT") data is "low delay". In other words, less delay is better.
Devices in a computer system, such as network adapters and disk drive adapters, are usually interconnected via a bus to permit the transfer of data from one device to another, and from one device to and from other system resources, such as the central processor and memory. Each of these devices has a particular type of data that it normally transfers, such as real time, loss sensitive or non-real time data. An arbiter is usually connected to the bus to make decisions as to which device will get current access to the bus. Thus, when two or more devices need to use the bus at the same time, the arbiter decides which device gets access and when.
In one advanced system (specifically, one employing the DEC 21150 PCI to PCI bridge chip, which includes a secondary bus arbiter), the bus arbiter uses a two level priority scheme and implements "fairness" within each priority group. With fairness, if there is more than one device of the same priority level requesting bus access at the same time, the arbiter rotates bus access from one device to the next, thereby preventing one device from monopolizing the bus. Fairness, however, does not cross the boundary between one priority level and another. Therefore, even with fairness, one or more high priority devices can potentially monopolize the bus from a low priority device, causing data loss for the low priority device.
Several schemes have been described that provide a trade-off between real time, non-real time and loss sensitive data traffic. In minimum laxity threshold ("MLT") scheduling, non-real time devices are serviced first, unless the "laxity" of a soft real time device is less than a threshold ("laxity threshold"). "Laxity" is the time remaining until a deadline is reached; in other words, the time preceding a deadline. And if the deadline is reached, data will be lost. Thus, MLT provides a near optimal trade-off between soft real time and non-real time data.
In minimum buffer threshold ("MBT") scheduling, non-real time data is serviced first, unless the buffer of a loss sensitive device is within a threshold ("buffer threshold") of overflowing. And if the buffer overflows, loss sensitive data will be lost. Thus, MBT provides a near optimal trade-off between loss sensitive and non-real time data traffic.
The problem with the MLT and MBT schemes, both of which have been previously proposed and studied, is that they are not implementable on a bus because the arbiter has no knowledge of the laxity thresholds of the soft real time devices, and the buffer thresholds of loss sensitive devices. Although it would be possible to add control lines to the bus whereby threshold and other information could be conveyed to the arbiter, one object of the present invention is to provide an improved scheduling scheme that does not require additional bus lines. Another object of the invention is to provide a scheduling system for transferring data over a bus that approximates the combined performance of both MLT and MBT schemes to provide near optimal trade-off between all fours types of data; hard real time, soft real time, loss sensitive and non-real time. To accomplish these and other objectives, the present invention uses a distributed scheduling scheme that puts part of the scheduling intelligence in the arbiter, and the other part in the devices themselves.